HW#3 --- last modified March 02 2019 21:25:32..

Solution set.

Due date: Mar 22

Files to be submitted:
  Hw3.tex
  Byzantine.zip

Purpose: To learn more about algorithms for parallel computation. To implement a distributed algorithm.

Specification:

Do problems 29.1-6, 29.2-1, 29.3-5 from Handout 1 and Exercise 12.2 p338 from Handout 2. Submit these problems in Hw3.tex.

For the coding part of the homework I would like you to code up the Byzantine agreement algorithm from Handout 2 and submit this in Byzantine.zip . Your program should consist of a driver class ElectionManager and another class Voter. The driver class should be run from the command line with a line like:

java ElectionManager number_of_voters number_faulty

The ElectionManager should then construct, initialize, and start number_of_voters many Voter objects. Of these, the first number_faulty should be faulty and the rest normal. The class Voter is a subclass of javax.swing.Timer which implements ActionListener. The constructor for this class takes an int delay and a boolean faultyNotFaulty and then call its parent's constructor with this delay and with argument null for the ActionListener. After the Voter is constructed use its addActionListener method with argument this so that it's actionPerformed method will be called when the timer goes off. Voter should have an internal field to store faultyNotFaulty. Voter should also have a int field roundNumber, which keeps track of which round in the agreement process we are at. This should initially be 0. The class ElectionManager should randomly choose the delay of each Voter object it creates from 1 mS to 5000 mS. As ElectionManager constructs each Voter it should add it to an ArrayList<Voter> object. Then when all of the Voter's have been constructed it should call each Voter's public void initialize(ArrayList<Voter> list) method to set an electorate field of each Voter object. Once this is done, the ElectionManager calls the start method of each Voter. The actionPerformed method of a Voter checks roundNumber. If this is zero, it immediately votes, outputs the vote to the standard output as well as which Voter it was, increments its roundNumber, and then informs all of the other Voter's. If this is greater than zero, it checks if it has received votes from all the other Voter's this round. If `no', actionPerformed finishes (and so the voter goes to sleep for delay mS). If `yes', it votes, outputs the vote to the standard output as well as which Voter it was, increments its roundNumber, and then informs all of the other Voter's. To vote, a Voter either follows the algorithm from the handout if it is normal and votes either 1 for heads or 0 for tails, or if its faulty, it should randomly choose between 1 or 0. To inform the other Voters, it iterates through its electorate ArrayList<Voter> and for each Voter other than itself, calls that Voter's, receiveVote(int i, Voter v) method with either 0 or 1 depending on its vote and with itself as the Voter. If following the algorithm from the book a Voter sets its vote value permanently then the Voter outputs which Voter it is followed by "Agreement reached !!", says what the agreement was, and then calls its stop() method. If a faulty voter ever sees that more than 7/8 th of the Voters vote the same way for two consecutive rounds it also prints its name and calls its halt method. The algorithm from the book uses a global coin. This can be implemented as a public static method in the ElectionManager named flip() which returns 0 or 1. The value of flip is randomly choosen the first time it is called. The next number_of_voter's many times it is called it stays constant, then a new coin flip is done, etc. If you modify the algorithm so as not to use a global coin you should say how and why your resulting protocol works in the comments in your files. (up to 2 point bonus for doing this well). It should be noted that the handout's faulty Voter can give a different vote value to each element in its list. If you like you can implement this more generalized faulty Voter or if you like stick with my simplified one. This method should increment the given Voter's vote count as well as increment either the heads or tails count depending on what the vote was.

Point Breakdown